package threshold;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-11 21:30
 * @Version 1.0
 */
public class FeiBoNa {

    /**
     * 斐波那契数列递归算法
     * @param n
     * @return
     */
    public int feiBoNa(int n){
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            return feiBoNa(n-1) + feiBoNa(n-2);
        }
    }

    /**
     * 斐波那契数列动态规划
     * @param n
     * @return
     */
    public int feiBoNaDp(int n){
        int[] ints = new int[n+1];
        ints[1] = 1;ints[0] = 0;
        for(int i=2;i<=n;i++){
            ints[i] = ints[i-1] + ints[i-2];
        }
        return ints[n];
    }

    /**
     * 斐波那契数列进阶
     * @param n
     * @return
     */
    public int feiBoNaDpPro(int n){
        int p=0,q=1,r=1;
        for(int i=2;i<=n;i++){
            r = p+q;
            p=q;
            q=r;
        }
        return r;
    }
    public static void main(String[] args) {
        FeiBoNa test = new FeiBoNa();
        System.out.println(test.feiBoNa(3));
        System.out.println(test.feiBoNaDp(10));
        System.out.println(test.feiBoNaDpPro(10));
    }
}
